import java.util.ArrayList;
import java.util.List;

class FindSame442 {
    /**
     * 题目核心 数据范围是有限制的 不用额外空间生成结果 数据重复最多两次 从而能推断出 使用数组下标 使用正负
     */
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            int num = Math.abs(nums[i]);
            if (nums[num-1] > 0) {
                nums[num-1] *= -1;
            }else{
                list.add(num);
            }
        }

        return list;
    }

    public static void main(String[] args) {
        int[] nums = { 4, 3, 2, 7, 8, 2, 3, 1 };
        new FindSame442().findDuplicates(nums);
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + ",");
        }
        System.out.println();
        System.out.println("*********************");
    }
}